
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 100    // 最大数组长度
#define MAX_RESULT 1000// 最大结果数量（排列数上限：100选10约1.7e13，需按需调整）

// 单个排列（存储n个字符串元素）
typedef struct {
    char* elements[MAX_LEN]; // 排列中的元素
    int len;                 // 排列长度（即n）
} Permutation;

// 结果集（存储所有排列）
typedef struct {
    Permutation* items; // 排列数组
    int count;          // 已存储的排列数量
    int capacity;       // 结果集容量
} ResultSet;

/**
 * 初始化结果集
 */
ResultSet* result_set_init(int capacity) {
    ResultSet* rs = (ResultSet*)malloc(sizeof(ResultSet));
    rs->items = (Permutation*)malloc(capacity * sizeof(Permutation));
    rs->count = 0;
    rs->capacity = capacity;
    return rs;
}

/**
 * 向结果集添加一个排列
 */
void result_set_add(ResultSet* rs, const char* elements[], int len) {
    if (rs->count >= rs->capacity) {
        fprintf(stderr, "结果集溢出！\n");
        return;
    }
    Permutation* p = &rs->items[rs->count++];
    p->len = len;
    for (int i = 0; i < len; i++) {
        p->elements[i] = (char*)malloc(strlen(elements[i]) + 1);
        strcpy(p->elements[i], elements[i]);
    }
}

/**
 * 拷贝字符串数组（辅助函数，对应Python remain[:]）
 */
char** copy_array(const char* src[], int len) {
    char** dest = (char**)malloc(len * sizeof(char*));
    for (int i = 0; i < len; i++) {
        dest[i] = (char*)malloc(strlen(src[i]) + 1);
        strcpy(dest[i], src[i]);
    }
    return dest;
}

/**
 * 从数组中删除指定索引的元素（辅助函数，对应Python copy.pop(i)）
 */
char** array_pop(const char* src[], int src_len, int idx, int* dest_len) {
    *dest_len = src_len - 1;
    char** dest = (char**)malloc(*dest_len * sizeof(char*));
    int dest_idx = 0;
    for (int i = 0; i < src_len; i++) {
        if (i == idx) continue;
        dest[dest_idx] = (char*)malloc(strlen(src[i]) + 1);
        strcpy(dest[dest_idx++], src[i]);
    }
    return dest;
}

/**
 * 释放字符串数组内存
 */
void free_array(char** arr, int len) {
    for (int i = 0; i < len; i++) {
        free(arr[i]);
    }
    free(arr);
}

/**
 * 释放结果集内存
 */
void result_set_free(ResultSet* rs) {
    for (int i = 0; i < rs->count; i++) {
        Permutation* p = &rs->items[i];
        for (int j = 0; j < p->len; j++) {
            free(p->elements[j]);
        }
    }
    free(rs->items);
    free(rs);
}

/**
 * 打印结果集（模拟Python列表输出格式）
 */
void print_result(ResultSet* rs) {
    for (int i = 0; i < rs->count; i++) {
        Permutation* p = &rs->items[i];
        printf("[");
        for (int j = 0; j < p->len; j++) {
            printf("\"%s\"", p->elements[j]);
            if (j != p->len - 1) {
                printf(", ");
            }
        }
        printf("]\n");
    }
}

/**
 * 递归访问函数（对应Python recursive_visit）
 * @param remain: 剩余元素数组
 * @param remain_len: 剩余元素个数
 * @param current: 当前已选元素数组
 * @param current_len: 当前已选元素个数
 * @param num: 还需选择的元素个数
 * @param rs: 结果集
 */
void recursive_visit(const char* remain[], int remain_len,
                     const char* current[], int current_len,
                     int num, ResultSet* rs) {
    if (num == 0) {
        result_set_add(rs, current, current_len);
        return;
    }

    for (int i = 0; i < remain_len; i++) {
        // 1. 拷贝剩余数组并删除第i个元素（对应Python copy = remain[:], copy.pop(i)）
        int new_remain_len;
        char** new_remain = array_pop(remain, remain_len, i, &new_remain_len);

        // 2. 构造新的当前数组（对应Python current_array + [x]）
        char** new_current = (char**)malloc((current_len + 1) * sizeof(char*));
        for (int j = 0; j < current_len; j++) {
            new_current[j] = (char*)malloc(strlen(current[j]) + 1);
            strcpy(new_current[j], current[j]);
        }
        new_current[current_len] = (char*)malloc(strlen(remain[i]) + 1);
        strcpy(new_current[current_len], remain[i]);

        // 3. 递归调用（num减1）
        recursive_visit(new_remain, new_remain_len, new_current, current_len + 1, num - 1, rs);

        // 4. 释放当前层分配的内存
        free_array(new_remain, new_remain_len);
        free_array(new_current, current_len + 1);
    }
}

/**
 * 递归法全排列（对应Python permutations）
 */
ResultSet* permutations_recursive(const char* array[], int array_len, int n) {
    if (n < 0 || n > array_len) {
        fprintf(stderr, "n必须在0~array_len之间！\n");
        return NULL;
    }
    ResultSet* rs = result_set_init(MAX_RESULT);
    char** empty_current = (char**)malloc(0); // 空数组（current初始值）
    recursive_visit(array, array_len, empty_current, 0, n, rs);
    free(empty_current);
    return rs;
}
// 栈元素结构（存储递归状态）
typedef struct {
    char** remain;     // 剩余元素数组
    int remain_len;    // 剩余元素个数
    char** current;    // 当前已选元素数组
    int current_len;   // 当前已选元素个数
    int num;           // 还需选择的元素个数
} StackItem;

/**
 * 非递归法全排列（对应Python栈模拟版）
 */
ResultSet* permutations_non_recursive(const char* array[], int array_len, int n) {
    if (n < 0 || n > array_len) {
        fprintf(stderr, "n必须在0~array_len之间！\n");
        return NULL;
    }
    ResultSet* rs = result_set_init(MAX_RESULT);

    // 初始化栈（最大深度：array_len，足够存储递归状态）
    StackItem stack[MAX_LEN];
    int stack_top = 0;

    // 1. 压入初始状态（剩余数组=原数组，当前数组=空，num=n）
    char** init_remain = copy_array(array, array_len);
    char** init_current = (char**)malloc(0); // 空数组
    stack[stack_top++] = (StackItem){init_remain, array_len, init_current, 0, n};

    // 2. 栈循环（LIFO特性，与Python结果顺序反向）
    while (stack_top > 0) {
        // 弹出栈顶元素
        StackItem item = stack[--stack_top];

        // 若还需选0个元素，加入结果集
        if (item.num == 0) {
            result_set_add(rs, item.current, item.current_len);
            // 释放当前状态的内存
            free_array(item.remain, item.remain_len);
            free_array(item.current, item.current_len);
            continue;
        }

        // 遍历剩余元素，构造新状态压入栈
        for (int i = 0; i < item.remain_len; i++) {
            // a. 拷贝剩余数组并删除第i个元素
            int new_remain_len;
            char** new_remain = array_pop(item.remain, item.remain_len, i, &new_remain_len);

            // b. 构造新的当前数组
            char** new_current = (char**)malloc((item.current_len + 1) * sizeof(char*));
            for (int j = 0; j < item.current_len; j++) {
                new_current[j] = (char*)malloc(strlen(item.current[j]) + 1);
                strcpy(new_current[j], item.current[j]);
            }
            new_current[item.current_len] = (char*)malloc(strlen(item.remain[i]) + 1);
            strcpy(new_current[item.current_len], item.remain[i]);

            // c. 压入栈（num减1）
            stack[stack_top++] = (StackItem){new_remain, new_remain_len, new_current, item.current_len + 1, item.num - 1};
        }

        // 释放弹出元素的内存（已构造新状态，原状态无需保留）
        free_array(item.remain, item.remain_len);
        free_array(item.current, item.current_len);
    }

    return rs;
}

int main() {
    // 测试数组（与Python一致）
    const char* array[] = {"A", "B", "C", "D"};
    int array_len = sizeof(array) / sizeof(array[0]);
    int n = 2;

    // 1. 测试递归法
    printf("递归法结果（与Python递归版顺序一致）：\n");
    ResultSet* rs_recur = permutations_recursive(array, array_len, n);
    print_result(rs_recur);
    result_set_free(rs_recur);

    // 2. 测试非递归法（栈模拟）
    printf("\n非递归法结果（与Python非递归版顺序一致）：\n");
    ResultSet* rs_non_recur = permutations_non_recursive(array, array_len, n);
    print_result(rs_non_recur);
    result_set_free(rs_non_recur);

    return 0;
}